package com.ifish.leetcode.problem.algorithm;

import com.ifish.leetcode.problem.BaseLeetCodeProblem;

/**
 * Created by iFish on 2017/7/9.
 */

public class _0005 extends BaseLeetCodeProblem {

    @Override
    public String title() {
        return "Longest Palindromic Substring";
    }

    @Override
    public int difficulty() {
        return 1;
    }

    @Override
    public void run() {
        super.run();

        String test = "babada";
        String sub = longestPalindrome(test);
        printResult(sub);
    }

    public String longestPalindrome(String s) {
        int begin = 0, end = 1;
        int len = s.length();

        for (int i = 0; i < len; i++) {
            if (len - 1 - i < (end - begin) / 2) {
                break;
            }

            int mb = i, me = i; // middle begin, middle end
            while (me + 1 < len && s.charAt(me) == s.charAt(me + 1)) {
                me++;
            }
            int b = mb, e = me; // true begin and true end
            while (b - 1 >= 0 && e + 1 < len && s.charAt(b - 1) == s.charAt(e + 1)) {
                b--;
                e++;
            }
            // record substring
            if (e - b + 1 > (end - begin)) {
                begin = b;
                end = e + 1;
            }
            // jump to next different char directly.
            i = me;
        }
        return s.substring(begin, end);
    }
}
